<!--
 * @Author: your name
 * @Date: 2021-07-20 14:47:24
 * @LastEditTime: 2021-07-21 23:33:30
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>哈希表实现</title>
</head>

<body>
  <script>
    // 封装哈希表类
    function HashTable() {
      // 属性
      this.storage = []
      this.count = 0 // 当前哈希表已经存放多少元素 count / limit = loadFactor(加载因子) > 0.75 数组需要扩容或减容
      this.limit = 7 // 当前哈希表数组总长度（质数）

      // 方法
      // 哈希函数
      HashTable.prototype.hashFunc = function (str, size) {
        // 1. 定义hashCode变量
        var hashCode = 0

        // 2. 霍纳算法，来计算hashCode的值
        // cats -> Unicode编码
        for (var i = 0; i < str.length; i++) {
          hashCode = 37 * hashCode + str.charCodeAt(i)
        }

        // 3. 取余操作
        var index = hashCode % size

        return index
      }

      // 插入&修改操作
      HashTable.prototype.put = function (key, value) {
        // 1. 根据key获取对应的index
        var index = this.hashFunc(key, this.limit)

        // 2. 根据index取出对应的bucket
        var bucket = this.storage[index]

        // 3. 判断该bucket是否为null
        if (bucket == null) {
          bucket = []
          this.storage[index] = bucket
        }

        // 4. 判断是否是修改数据
        for (var i = 0; i < bucket.length; i++) {
          var tuple = bucket[i]
          if (tuple[0] === key) {
            tuple[1] = value
            return
          }
        }

        // 5. 进行添加操作
        bucket.push([key, value])
        this.count += 1

        // 6. 判断是否需要扩容操作
        if (this.count > this.limit * 0.75) {
          var newSize = this.limit * 2
          var newPrime = this.getPrime(newSize)
          this.resize(newPrime)
        }
      }

      // 获取操作
      HashTable.prototype.get = function (key) {
        // 1. 根据key获取对应的index
        var index = this.hashFunc(key, this.limit)

        // 2. 根据index取出对应的bucket
        var bucket = this.storage[index]

        // 3. 判断该bucket是否为null
        if (bucket == null) {
          return null
        }

        // 4. 线性查找bucket
        for (var i = 0; i < bucket.length; i++) {
          var tuple = bucket[i]
          if (tuple[0] === key) {
            return tuple[1]
          }
        }

        // 5. 依然没有找到
        return null
      }

      // 删除操作
      HashTable.prototype.remove = function (key) {
        // 1. 根据key获取index
        var index = this.hashFunc(key, this.limit)

        // 2. 根据index获取bucket
        var bucket = this.storage[index]

        // 3. 判断bucket是否存在，如果不存在直接返回null
        if (bucket == null) {
          return null
        }

        // 4. 线性查找bucket，寻找对应的数据，并且删除
        for (var i = 0; i < bucket.length; i++) {
          var tuple = bucket[i]
          if (tuple[0] === key) {
            bucket.splice(i, 1)
            this.count--

            // 缩小容量
            if (this.limit > 7 && this.count < this.limit * 0.25) {
              var newSize = Math.floor(this.limit / 2)
              var newPrime = this.getPrime(newSize)
              this.resize(newPrime)
            }
            return tuple[1]
          }
        }

        // 5. 依然没有找到 返回null
        return null
      }

      // 其他方法
      // 判断哈希表是否为空
      HashTable.prototype.isEmpty = function () {
        return this.count === 0
      }

      // 获取哈希表的个数
      HashTable.prototype.size = function () {
        return this.count
      }

      // 哈希扩容&缩容
      HashTable.prototype.resize = function (newLimit) {
        // 1. 保存旧的数组内容
        var oldStorage = this.storage

        // 2. 重置所有的属性
        this.storage = []
        this.count = 0
        this.limit = newLimit

        // 3. 遍历oldStorage中所有的bucket
        for (var i = 0; i < oldStorage.length; i++) {
          // 3.1 取出对应的bucket
          var bucket = oldStorage[i]

          // 3.2 判断bucket是否为null
          if (bucket === null) {
            continue
          }

          // 3.3 bucket中有数据，那么取出数据重新插入
          for (var j = 0; j < bucket.length; j++) {
            var tuple = bucket[j]
            this.put(tuple[0], tuple[1])
          }
        }
      }

      // 判断某个数字是否是质数
      HashTable.prototype.isPrime = function (num) {
        // 1. 获取num的平方根
        var temp = parseInt(Math.sqrt(num))

        // 2. 循环判断
        for (var i = 2; i <= temp; i++) {
          if (i % 2 === 0) {
            return false
          }
        }

        return true
      }

      // 获取质数
      HashTable.prototype.getPrime = function (num) {
        while (!this.isPrime(num)) {
          num++
        }
        return num
      }
    }

    var hash = new HashTable()

    hash.put('abc', '123')
    hash.put('cba', '321')
    hash.put('nba', '521')
    hash.put('mba', '520')

    console.log(hash.get('abc'))

    hash.put('abc', '111')

    console.log(hash.get('abc'))

    hash.remove('abc')

    console.log(hash.get('abc'))
  </script>
</body>

</html>